﻿template<class T>
struct BTNode
{
	T data;
	BTNode <T>* Lchild, *Rchild;
	BTNode(T nodeValue = T(), BTNode<T>* leftNode = NULL, BTNode<T>* rightNode = NULL) :data(nodeValue), Lchild(leftNode), Rchild(rightNode) {}
	template <class T>
	void createBinTree(BTNode<T>*& root)
	{
		BTNode<T>* p = root;
		BTNode<T>* k;
		T nodeValue;
		cin >> nodeValue;
		if (nodeValue == -1)
		{
			root = NULL;
		}
		else
		{
			root = new BTNode<T>();
			root->data = nodeValue;
			createBinTree(root->Lchild);
			createBinTree(root->Rchild);
		}
	}
	template <class T>
	void preOrder(BTNode<T>*& p)
	{
		if (p)
		{
			cout << p->data << " ";
			preOrder(p->Lchild);
			preOrder(p->Rchild);
		}
	}
	template<class T>
	void inOrder(BTNode<T>*& p)
	{
		if (p)
		{
			inOrder(p->Lchild); cout << p->data << " ";
			inOrder(p->Rchild);
		}
	}
	template <class T>
	void levelOrder(BTNode<T>*& p)
	{
		if (p)
		{
			levelOrder(p->Lchild);
			levelOrder(p->Rchild);
			cout << p->data << " ";
		}
	}
	template<class T>
	int countNode(BTNode<T>*& p)
	{
		if (p == NULL) return 0;
		return 1 + countNode(p->Lchild) + countNode(p->Rchild);
	}
	template<class T>
	int depth(BTNode<T>*& p)
	{
		if (p == NULL)
			return -1;
		int h1 = depth(p->Lchild);
		int h2 = depth(p->Rchild);
		if (h1 > h2)return(h1 + 1);
		return h2 + 1;
	}
	template<class T>
	BTNode<T>* destroy(BTNode<T>* p)